home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / INTERNET / SITES / RAND / T0307 / text0033.txt < prev    next >
Encoding:
Text File  |  1997-02-06  |  6.7 KB  |  176 lines
  1. Hi,
  2. i've just seen a message from Doug about the AI.
  3. i'll read it further tonight.
  4.  here's an introduction file i've made. Waiting for comments...
  5. BTW, it's not finished, i'll keep it up to date.
  6.  
  7. --------------------------------------------------------------------------
  8. Bad Mood - Basic Monster AI - 
  9. Frederic Jaume 21.02.96 jaume@massilia.univ-mrs.fr
  10. With the help of Frederic Calendini
  11. Changes : 06.03.96 
  12.  
  13. here's just a first try, tell me what you think.
  14. There are a lot of question in the following document, so please
  15. answer them! 
  16.  
  17. Part one : the monsters and other things...
  18. First, we need to choose a data structure, and then to create the AI.
  19. thhen I 'll  explain the method that can be used for the monsters movements.
  20. This method works! It's not very complex for the moment, but it's been used 
  21. in a game (that was done by a friend of mine) on amiga, some sort of Zelda/Ultima
  22. adventure game that had to deal with monsters AI. Though, it was programmed in AMOS, 
  23. and neither my friend nor i, can code in 68030, so you'll just find algorithms, and 
  24. simple C code. Bad Mood deserves a more complex AI, but it's just 
  25. a beginning.
  26.  
  27.         --------------------------------
  28.  
  29. An inportant part of the AI is the data structures to be used.
  30.  
  31. DATA STRUCTURES
  32.  
  33. Al the 'Things' in the doom.wad's level chosen should be stored in an
  34. array. Each element of the array, each 'Thing' has :
  35. 1- x
  36. 2- y
  37. 3- facing angle
  38. 4- thing type
  39. 5- thing option
  40. (to be modified when our own Bad Mood Thing specs are done)
  41. And stored in a table should be also in memory the Things characterisic
  42. (i.e. Radius, Height, Mass, Tough, Speed,  Sprite name or class of things)
  43. correspond to a special Thing Type.
  44.  
  45. As Doug suggested, the use of linked list may be the more effective for
  46. knowing what 'Things' has to be dealt with.
  47. The list are built using the sector number.
  48. Let's say there are n sectors in the chosen levels. Then we create n lists
  49. of chained things (or rather chained pointers on elements of the Things
  50. array). And, when the player gets in sector x, the 'things' in the list x 
  51. are used and treated. 
  52.  
  53. >>? Should we use the same sector numbering as the one used to build up 
  54.   levels, since there are a lot of them, and some of them will not have 
  55.   'things' inside (the small ones).
  56.  
  57. Now, 2 possibilities:
  58. (look at drawing) what if you are in 1 (then checking things in     
  59. list1) ? We have to also check the things in 2 and 3 (they might see you, 
  60. you might see them) [think also of monsters behind windows like in e1m1]
  61.  
  62.  
  63.                        |2|
  64.                 _______| |   
  65.               /          |______
  66.               |              3
  67.               |           ______
  68.               |          |
  69.               |    1     |
  70.               \__________/
  71.     
  72. So, either we have 1 list for sector 1 that contains all the things 
  73. in sector 1 but also contains the things from close sectors (2 and 3), and 
  74. then we only check the list the player is in,
  75. or, we have in each list only the things of the sector which corresponds 
  76. to the list, and we have top check multiple list each time, i.e. the list 
  77. the player is in, and the list of the close sectors. (better for memory). 
  78.  
  79. If a monster changes sector (chasing you), he is removed from the list he 
  80. belonged(involves a search), and added to the list of the new sector he is
  81. in).
  82. If a monster is killed, then he becomes an inanimate object (dead body).
  83. If a thing is taken (key, medicine) then it is removed from the list it 
  84. belongs to. 
  85.  
  86. to be continued...
  87.  
  88.  
  89.  
  90.  
  91. THE AI - 'INVISIBLE FOOTPRINTS' METHOD 
  92.  
  93.  
  94. - how does it work ?
  95. to simulate a realistic chase, we can use the "invisible footprints/trail" 
  96. method, which is the following one: 
  97. we've got an array of that type:
  98.  
  99. typedef struct footprint { int x,y }
  100.  
  101. struct footprint trail[max_number_of_footprints]
  102.  
  103. let's say max_number_of_footprints=20, then we've got the 20 last positions 
  104. of the player in memory all the time. What's the point?
  105.  
  106. Well, here's the basic algorithm:
  107.  
  108.  
  109. loop
  110. {
  111.  for i <- 0 to nb_things_in_current_sector
  112.  begin
  113.    if thing[i] is a monster then
  114.      if this monster "sees" the player then
  115.         monster steps toward the player
  116.         if distance between monster and player is <= min_dist then fire!
  117.      else 
  118.      repeat    
  119.        check each player_footprint (from new one to old one)
  120.        if monster sees footprint, then he steps toward this position
  121.      until (monster moved) or (all fooprints checked)
  122.     /* if monsters doesn't see any footprints then monster stops */
  123.    else: nothing 
  124.  end
  125. }
  126.  
  127. an interesting point is that, with this method we can have an intelligence 
  128. factor for each monster, which is in fact the ability of the monster to 
  129. see a particular amount of footprints (dumb monsters won't see any, so if 
  130. you just hide behind a wall, the dumb monsters think you disapeared, and 
  131. go back to watch BayWatch...
  132.  
  133.  
  134. When a monster follows the player into a sector which is not his (this 
  135. happens if the monster is not blocked by the Reject), then he is 
  136. deleted from the list of the sector to which he belongs, and added to the 
  137. list of the one he arrives in.
  138.  
  139. Of course, this still makes dumb monsters, very easy to shoot, so 
  140. they'll have to zig-zag to try to avoid your shooting, like in doom, 
  141. maybe we can think of differents moves, using differents formulas so 
  142. that all the monsters don't act the same way.   
  143.  
  144. And, can't the monster find you by the noise you make ( in the Mexican 
  145. Food Inferno level...) ?
  146.  
  147. I though about it, and i think we can do it by generating footprints all 
  148. around the player (in every direction, in places that are step-able)
  149. whenever he uses a noisy weapon. But, then we need 
  150. another structure for noise generated footprints (as when in chase mode we 
  151. need an ordered list of footprints), so the foot-made footprints are
  152. checked first, and then the noise-prints second.
  153.  
  154. And now for something completely different :
  155. What is needed:
  156. -thing-player collision 
  157. -monster-sees-player function
  158. -sector-thing-is-in-function
  159. -speed optimization
  160.  
  161. This is a cut version. I want some feed back!
  162. I've got some C code, too but it's not good enough at the moment.
  163.  
  164. Bye!
  165. XxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxX
  166. X        Information is not knowledge , knowledge is not wisdom               X
  167. X                 Wisdom is not truth , thruth is not beauty                  X
  168. X                  Beauty is not Love , Love is not Music                     X
  169. X                          Music is the Best !    (Frank Zappa)               X
  170. X                                                                             X
  171. X            Frederic JAUME --->   jaume@massilia.univ-mrs.fr                 X
  172. X     Licence d'Informatique   CMI Chateau-Gombert Marseille, FRANCE          X
  173. XxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxX
  174.  
  175.  
  176.